public class Leetcode1335 {

    public static int minDifficulty(int[] jobDifficulty, int d) {
        if (d > jobDifficulty.length) {
            return -1;
        }
        Integer[][] job = new Integer[jobDifficulty.length + 1][d + 1];

        return minDifficulty(job, jobDifficulty, 0, d);
    }

    public static int minDifficulty(Integer[][] job,
                                    int[] jobDifficulty,
                                    int startIndex,
                                    int d) {
        if (job[startIndex][d] != null) {
            return job[startIndex][d];
        }

        if (d == 1) {
            int cur = 0;
            for (int i = startIndex; i < jobDifficulty.length; i++) {
                if (jobDifficulty[i] > cur) {
                    cur = jobDifficulty[i];
                }
            }

            return cur;
        }

        int res = Integer.MAX_VALUE;
        int max = 0;
        for (int i = startIndex; i <= jobDifficulty.length - d; i++) {
            max = Math.max(max, jobDifficulty[i]);
            int difficulty = max;

            int s = minDifficulty(job, jobDifficulty, i + 1, d - 1);
            difficulty += s;

            if (difficulty < res) {
                res = difficulty;
            }
        }

        job[startIndex][d] = res;

        return res;
    }

    /**
     * 7
     * -1
     * 3
     * 15
     * 843
     * 3807
     *
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(minDifficulty(new int[]{6, 5, 4, 3, 2, 1}, 2));
        System.out.println(minDifficulty(new int[]{9, 9, 9}, 4));
        System.out.println(minDifficulty(new int[]{1, 1, 1}, 3));
        System.out.println(minDifficulty(new int[]{7, 1, 7, 1, 7, 1}, 3));
        System.out.println(minDifficulty(new int[]{11, 111, 22, 222, 33, 333, 44, 444}, 6));
        System.out.println(minDifficulty(
                new int[]{380, 302, 102, 681, 863, 676, 243, 671, 651, 612, 162, 561, 394, 856, 601, 30, 6, 257, 921, 405, 716, 126, 158, 476, 889, 699, 668, 930, 139, 164, 641, 801, 480, 756, 797, 915, 275, 709, 161, 358, 461, 938, 914, 557, 121, 964, 315},
                10
        ));
    }

}

